﻿#pragma once
#include "Index.h"
#include "SearchRangeInOrderedArr.h"

/**
 * 在排序数组中查找数字I.
 * 数组 二分查找
 * https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 *
 * 统计一个数字在排序数组中出现的次数
 */
namespace NumOccurInOrderedArray
{
	class Question
	{
	public:
		virtual int countTarget(std::vector<int>& orderedNums, int target) = 0;
	};

	class Binary :public Question
	{
	public:
		int countTarget(std::vector<int>& orderedNums, int target) override
		{
			SearchRangeInOrderedArr::Binary searchRange;
			auto rangeIndices = searchRange.searchRange(orderedNums, target);

			if (rangeIndices.empty() || rangeIndices.front() < 0)
				return 0;
			return rangeIndices[1] - rangeIndices[0] + 1;
		}
	};

	class CallAPI:public Question
	{
	public:
		int countTarget(std::vector<int>& orderedNums, int target) override
		{
			if(orderedNums.empty())
				return 0;
			auto lower_iter= std::lower_bound(orderedNums.begin(),orderedNums.end(),target);
			auto upper_iter=std::upper_bound(orderedNums.begin(),orderedNums.end(),target);
			const int occur_count= upper_iter-lower_iter;
			return occur_count;
		}
	};

	class Practice:public Question
	{
	public:
		int countTarget(std::vector<int>& orderedNums, int target) override
		{
			if(orderedNums.empty())
				return 0;
			int lower_pos= binaryLowerBound(orderedNums,0,orderedNums.size()-1,target);
			int upper_pos=binaryUpperBound(orderedNums,0,orderedNums.size()-1,target);
			return upper_pos-lower_pos;
		}
	private:
		//在nums数组的 [left,right]位置区间上找第一个大于等于target的位置
		//输入的参数nums数组已保证按照非递减顺序排列
		int binaryLowerBound(const std::vector<int>& nums,int left,int right,const int target)
		{
			if(nums.empty() || left>right)
				return -1;

			int lower_pos=right+1;//相当于没找到时返回 nums.end()的迭代器位置

			while(left <= right)
			{
				int mid=left+((right-left)>>1);
				if(nums[mid] >= target)
				{
					lower_pos=mid;
					right=mid-1;
				}
				else
				{
					left=mid+1;
				}
			}
			return lower_pos;
		}

		//在nums数组的 [left,right]位置区间上找第一个大于target的位置
		//输入的参数nums数组已保证按照非递减顺序排列
		int binaryUpperBound(const std::vector<int>& nums,int left,int right,const int target)
		{
			if(nums.empty() || left>right)
				return -1;
			int upper_pos=right+1;//相当于没找到时返回 nums.end()的迭代器位置
			while(left <= right)
			{
				int mid=left+(right-left>>1);
				if(nums[mid]>target)
				{
					upper_pos=mid;
					right=mid-1;
				}
				else
				{
					left=mid+1;
				}
			}
			return upper_pos;
		}
	};
}